package com.fang.algorithm.leecode;

import java.util.Arrays;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 快速排序
 * @date 2022/2/22 8:47 下午
 **/
public class Test09_QuickSort {
    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 6, 7, 8, 9, 2, 1, 3};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private static void quickSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }

    private static void process(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] pivot = partition(nums, left, right);
        process(nums, left, pivot[0] - 1);
        process(nums, pivot[1] + 1, right);
    }

    private static int[] partition(int[] nums, int left, int right) {
        // 小于标准值区域右边界
        int lessR = left - 1;
        // 大于标准值区域左边界
        int moreL = right;
        // 当前索引位置
        int currIndex = left;
        while (currIndex < moreL) {
            if (nums[currIndex] < nums[right]) {
                // 当前位置的值小于标准值 当前值和小于标准值区域的下一个位置的值交换 并且 当前位置右移
                swap(nums, ++lessR, currIndex++);
            } else if (nums[currIndex] > nums[right]) {
                // 当前位置的值大于标准值 当前值和大于标准值区域左边界的上一个位置的值交换 当前位置不动
                swap(nums, currIndex, --moreL);
            } else {
                // 相等则不改变 当前位置右移
                currIndex++;
            }
        }
        // 让标准值和大于标准值区域的位置交换
        swap(nums, moreL, right);
        // 返回和标准值相等区域的左右边界
        return new int[]{lessR + 1, moreL};
    }

    private static void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
